package demo.letcode.top100;

import java.util.Arrays;

/**
 * 给你一个包含n个整数的数组nums，判断nums中是否存在三个元素a,b,c
 * 使得a+b+c=0?找出所有和为0切不重复的三元组
 * 注 答案中不可以包含重复的三元组
 * <p>
 * 输入 nums=[-1,0,1,2,-1,-4]
 * 输出 {[-1,-1,2],[-1,0,1]}
 * <p>
 * 输入nums=[]
 * 输出[]
 *
 * @author taqo
 * @date 2021/5/7
 */
public class _15三数之和 {
    public static void main(String[] args) {
        int a[] = {-1, 0, 1, 2, -1, -4};

        Arrays.sort(a);
        int b[][] = new int[a.length][];
        System.out.println(Arrays.toString(a));
        for (int i = 0; i < a.length; i++) {
            if (a[i] > 0) {
                break;
            }

            int j = i + 1;
            int k = a.length - 1;
            int sum = 0;
            while (j<k){
                sum = a[i] + a[j] + a[k];
                if (sum == 0) {
                    // 去重
                    while (j<k && a[j] == a[j+1]) {
                        j++;
                    }
                    while (j<k && a[k] == a[k-1]) {
                        k--;
                    }

                    System.out.println(a[i]);
                    System.out.println(a[j]);
                    System.out.println(a[k]);
                    break;
                } else if (sum <0) {
                    j++;
                } else {
                    k--;
                }
            }
        }

    }
}
